package model;

/**
 * This class allows us to find a LCS using a dynamic approach
 * 
 * @author Elias
 */
public class LCS_dynamic {

	/**
	 * This function returns the LCS between a and b
	 * 
	 * @param a
	 *            the first sequence
	 * @param b
	 *            the second sequence
	 * @return the lcs
	 */
	public static String lcs(String a, String b) {
		int aLen = a.length();
		int bLen = b.length();
		StringBuffer sb = new StringBuffer();
		int[][] tab = new int[aLen + 1][bLen + 1];

		for (int i = 0; i < aLen; i++)
			for (int j = 0; j < bLen; j++)
				if (a.charAt(i) == b.charAt(j)) {
					tab[i + 1][j + 1] = tab[i][j] + 1;
				} else {
					tab[i + 1][j + 1] = Math.max(tab[i + 1][j], tab[i][j + 1]);
				}

		for (int x = aLen, y = bLen; x > 0 && y > 0;) {
			if (tab[x][y] == tab[x - 1][y]) {
				x--;
			} else if (tab[x][y] == tab[x][y - 1]) {
				y--;
			} else {
				x--;
				y--;
				assert a.charAt(x) == b.charAt(y);
				sb.append(a.charAt(x));
			}
		}
		return sb.reverse().toString();
	}
}
